// 给定一个长度为n的数组nums，nums包含[0, n]中的n个数，要求找出[0, n]范围内没有出现在数组中的那个数, nums中的数字是唯一的

// 思路1：哈希表
// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(n)

function missingNumber(arr) {
    let set = new Set(arr)
    let n = arr.length
    for (let i = 0; i <= n; i++) {
        if (!set.has(i)) {
            return i
        }        
    }
}

// 思路2：数学运算
// 时间复杂度：O(n)，n是数组的长度
// 空间复杂度：O(1)

function missingNumber2(arr) {
    let sum = 0
    let n = arr.length
    for (let i = 0; i < n; i++) {
        sum += arr[i]        
    }
    return Math.floor(n * (n + 1) / 2) - sum
}

// 思路3：排序后判断
// 时间复杂度：O(nlogn)，n是数组的长度
// 空间复杂度：O(1)

function missingNumber3(arr) {
    arr.sort((a, b) => a - b)
    for (let i = 0; i <= arr.length; i++) {
        if (i !== arr[i]) {
            return i
        }        
    }
    // 这个最终返回
    return arr.length
}